package algorithm.leetcode.medium;

/*
 给出一个区间的集合，请合并所有重叠的区间。
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/9
 */
public class Question56 {

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        Question56 question = new Question56();
        int[][] merge = question.merge(intervals);
        for (int[] r : merge) {
            System.out.println(Arrays.toString(r));
        }
    }

    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>(10);
        if (intervals == null || intervals.length == 0) {
            return res.toArray(new int[0][2]);
        }
        // 左区间排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int i = 0;
        while (i < intervals.length) {
            // 左区间
            int left = intervals[i][0];
            // 右区间
            int right = intervals[i][1];
            // 这么做的前提就是 对左区间排序
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            res.add(new int[]{left, right});
            i++;
        }
        return res.toArray(new int[0][2]);
    }

}
